/*
MIF32 TP5
ROUX Steve  10607327 
XIAO Yang  10609286
*/


#include "arch.h"
#include <stdlib.h>
#include <time.h>
#include <math.h>

/*Taille de la matrice d'adjacence (matrice carrée)*/
#define N 6
/*Taille de la matrice des processeurs (matrice carrée*/
#define P 3

#define _INFINITE 0

//#define CHRONO_MODE

clock_t c_start, c_end;
double mpi_start, mpi_end, mpi_elapsed, c_elapsed;

/* Nombre de ligne dans la matrice*/
int MATRIX_SIZE;

/* Calcul des tailles des sous univers */
double d_sqrt_pn;
int sqrt_pn;

/* Identifiants globaux */
Coll_id cid[10];
Coll_id cid1;
Global_id gid1,gid2;

/*Table contenant les matrices*/
class Tableau
{
public:
	int table[N/P][N/P];

/*	int **table;
	Tableau()
	{
		table = new  int*[N/P];

		for(int i=0; i<(N/P); i++) 
		{
			table[i] = new  int[N/P];
		}
	}

	~Tableau()
	{
		for(int i=0; i<N/P; i++)
		{
			delete[] table[i];
		}
	
		delete[] table;
		table = NULL;
	}
*/
};

/*Déclaration des canaux de communication*/
ChanRD<Tableau> *proc_to_same_col_plus_un;
ChanRD<Tableau> *proc_to_same_col_moins_un;

/* Initialisation */
void init(int, char **)
{
	for(int i  = 0; i < P; i++)
	{
		cid[i].set();
	}
	gid1.set();gid2.set();
	cid1.set();
}

/* Definition du role de chaque processeur*/
int role (int h, int v, int k)			// ex : h=1	v=2	k=2
{
	int d = v - h;				// d = 1 - 2 = -1

	if(d<0)
		d=d+sqrt_pn;				// d = -1 + 3 = 2
	if(d==k)
		return 1; // l'emmeteur		// d=k donc emmeteur
	else
		return 0; // récepteur
}

/* Definition du graphe */
int **matrix;

/*Construction de la matrice*/
void construire_matrix()
{
	matrix = new  int*[MATRIX_SIZE];

	for(int i=0; i<MATRIX_SIZE; i++) 
	{
	matrix[i] = new  int[MATRIX_SIZE];

		for(int j=0; j<MATRIX_SIZE; j++) {
			if( (i + j)%2 ) 
			{
				/* Construction d'un graphe sous la forme d'un arbre (pas de boucle de longueur négative*/
				if (j<i)
					matrix[i][j] = _INFINITE;
				else 
					matrix[i][j] = i + j;
			}
			else {
				matrix[i][j] = _INFINITE;
			}
		}
	}
}

void afficher_matrix ()
{
	for(int i=0; i<MATRIX_SIZE; i++) 
	{
	fprintf(Sdf::trace,"--- matrix -> ",Sdf::PROC_ID);
		for(int j=0; j<MATRIX_SIZE; j++) 
		{
			fprintf(Sdf::trace," %d ",matrix[i][j]) ;
		}
	fprintf(Sdf::trace,"\n");
	fflush(Sdf::trace);
	}
fprintf(Sdf::trace,"\n");

}

void afficher_matrix_locale (char tag, Tableau _T)
{
	for(int i=0; i<N/P; i++) 
	{
		fprintf(Sdf::trace,"node %d : %c -> ",Sdf::PROC_ID,tag);
		for(int j=0; j<N/P; j++) 
		{
			fprintf(Sdf::trace," %d ",_T.table[i][j]) ;
		}
	fprintf(Sdf::trace,"\n");
	}
	fprintf(Sdf::trace,"\n");
	fflush(Sdf::trace);

}

/* Destruction de la matrice*/
void detruire_matrix() {
	
	for(int i=0; i<MATRIX_SIZE; i++) {
	
		delete[] matrix[i];
	}
	
	delete[] matrix;
	
	matrix = NULL;
}

/* Classe principale */
class Root_thread: public Thread{
private:

int v_index,h_index;
int g_root; /* Processeurs émetteur dans le sous univers */

int proc_id;
Tableau A,B,C,A_recu,B_temp,T;
int    *rank;
Group **group;
CommL **comml;

public:

	Root_thread(): Thread((Tmf0_ptr)&Root_thread::body) {}

	~Root_thread() {}

	void body()
	{
	if (Verif())
	{

		#ifdef CHRONO_MODE
		/* Lancement de la mesure */
		c_start = clock();
		mpi_start = MPI_Wtime();
		#endif

		fprintf(Sdf::trace,"\n");
		fflush(Sdf::trace);

		proc_id = Sdf::PROC_ID;

		sqrt_pn = P;
		MATRIX_SIZE= N;

		/* Calcul des positions v et h de chaque processeur dans la matrice des processeurs*/
                h_index = proc_id/sqrt_pn;
                v_index = proc_id%sqrt_pn;

		/* Chaque processus construit la meme matrice */
		construire_matrix();

		if(proc_id==0)
		{
			#ifdef CHRONO_MODE		
			fprintf(Sdf::trace,"--- \t\t CHRONO_MODE \n",Sdf::PROC_ID);
			#endif
			#ifndef CHRONO_MODE		
			fprintf(Sdf::trace,"--- \t\t NORMAL_MODE\n",Sdf::PROC_ID);
			afficher_matrix();
			#endif
		}

		/* Répartition des éléments de la matrice + initialisation de C */
		for (int i=0; i < N/P; i++ )
		{
			for(int j=0; j<N/P; j++)
			{
				A.table[i][j] = matrix[((h_index*(N/P))+i)][((v_index*(N/P))+j)];
			} 
		}
		
		/*Initialiser les canaux de communication*/
               	int col_id_plus_un 	= (proc_id+sqrt_pn)% (P*P);
		int col_id_moins_un 	= (proc_id-sqrt_pn)% (P*P);

		if (col_id_moins_un < 0) col_id_moins_un = (P*P) + col_id_moins_un;

                proc_to_same_col_plus_un  = new ChanRD<Tableau>(gid1, col_id_plus_un);
		proc_to_same_col_moins_un = new ChanRD<Tableau>(gid2, col_id_moins_un);

		/***Contruire l'arbre de diffusion broadcast***/
		/*Rang du processeurs dans la liste des processeurs*/
                rank = new int[Sdf::PROC_NB];
                int i;
                for(i  = 0; i < Sdf::PROC_NB; i++)
                   rank[i] = i;

		/* Création d'un sous univers de communication */
               group = new Group*[sqrt_pn];
               comml = new CommL*[sqrt_pn];

               for(i = 0; i < sqrt_pn; i++){
                   group[i] = Sdf::incl(Sdf::COMML_WORLD, sqrt_pn, rank + i*sqrt_pn);
                   comml[i] = group[i]->commit(cid[i], Sdf::COMML_WORLD);
                }
		
		#ifndef CHRONO_MODE
		fprintf(Sdf::trace,"node %d --- Début de l'algorithme \n",proc_id);
		fflush(Sdf::trace);
		#endif

		/*Début de l'algorithme*/	
		B = A;
		C = A;

		if (Sdf::PROC_NB ==1)
		{
			//not completed
			fprintf(Sdf::trace,"! Not completed \n",Sdf::PROC_ID);
			fflush(Sdf::trace);
		}
		else
		{
			for (int k = 0; k < sqrt_pn ;k++)
			{
				
				g_root = (h_index+k)%sqrt_pn;
				
				if (role (h_index,v_index,k))
				{
					/*Participer à la diffusion du bloc A en tant qu'émeteur(g_root)*/
					_Sdf<Tableau>::bcast(A, 1, g_root, cid[h_index], comml[h_index]);
					/*C = C + A x b*/
	
					T = prod_matriciel( A , B );
					C = min(C,T);
	
					#ifndef CHRONO_MODE
					fprintf(Sdf::trace,"node %d (Emmeteur) end h=%d v=%d k=%d \n",proc_id,h_index,v_index,k);
					fflush(Sdf::trace);
					#endif
	
	
				}else
				{
					/*Participer à la diffusion du bloc A en tant que récepteur*/
					_Sdf<Tableau>::bcast(A_recu, 1, g_root, cid[h_index], comml[h_index]);
					/*C = C + A_recu x b*/
					T = prod_matriciel( A_recu , B );
					C = min(C,T);
	
					#ifndef CHRONO_MODE
					fprintf(Sdf::trace,"node %d (Recepteur) End h=%d v=%d k=%d \n",proc_id,h_index,v_index,k);
					fflush(Sdf::trace);
					#endif
				}
	
	
				A=C;
	
				if (h_index==0)
				{
					#ifndef CHRONO_MODE
					fprintf(Sdf::trace,"node %d Reception du bloc B \n",proc_id);
					fflush(Sdf::trace);
					#endif
	
					/* Recevoir bloc B, même colonne, à h+1 modulo p*/
					proc_to_same_col_plus_un->recv(B_temp);	//B_temp pour ne pas fausser le vrai B
				}
					
					#ifndef CHRONO_MODE
					fprintf(Sdf::trace,"node %d Envoi du bloc B \n",proc_id);
					fflush(Sdf::trace);
					#endif
	
					/* Envoyer bloc B, même colonne, à h-1 modulo p*/
					proc_to_same_col_plus_un->send(B);
					B=B_temp;
			
				if (h_index!=0)
				{
					#ifndef CHRONO_MODE
					fprintf(Sdf::trace,"node %d Reception du bloc B \n",proc_id);
					fflush(Sdf::trace);
					#endif
	
					/* Recevoir bloc B, même colonne, à h+1 modulo p*/
					proc_to_same_col_plus_un->recv(B);	
				}
				/*Attendre fin d'émission et de reception*/	
				Sdf::barrier(cid1);
			}
		}

		#ifndef CHRONO_MODE		
		fprintf(Sdf::trace,"node %d --- Fin de l'algorithme \n",proc_id);
		afficher_matrix_locale('R',A);
		#endif

		#ifdef CHRONO_MODE 
		/* Arret de la mesure */
		c_end = clock();	
		mpi_end = MPI_Wtime();		
		c_elapsed = ((double)c_end - c_start) / CLOCKS_PER_SEC;	/* Conversion en seconde */
		mpi_elapsed = mpi_end - mpi_start;	

		fprintf(Sdf::trace,"Temps d'execution sur proc %d: c:%4.4f, mpi:%4.4f ( nb sommets:%d, nb proc:%d ) \n",Sdf::PROC_ID,c_elapsed,mpi_elapsed,MATRIX_SIZE,Sdf::PROC_NB);
		fflush(Sdf::trace);		
		#endif

		/*Destructions*/
              	for(i  = 0; i < sqrt_pn; i++)
                   delete comml[i];

                delete []comml;
                delete []group;
                delete []rank;
		delete proc_to_same_col_plus_un;
		delete proc_to_same_col_moins_un;
	}
	}

protected :

	/*Fonction qui calcule le minimum */
	Tableau min(Tableau _C, Tableau _Resultat_ProdMat)
	{
		for (int i=0; i<N/P;i++)
		{	
			for(int j=0; j<N/P;j++)
			{
				if ((( _Resultat_ProdMat.table[i][j] < _C.table[i][j])	   ||(_C.table[i][j]==_INFINITE))&&(_Resultat_ProdMat.table[i][j]!=_INFINITE))
						_C.table[i][j] = _Resultat_ProdMat.table[i][j];

			}
		}
		return _C;
	}

	/*Produit matriciel*/
	Tableau prod_matriciel (Tableau _A, Tableau _B)
	{
		Tableau _Resultat;

		for (int i=0; i<N/P;i++)
		{
			for (int j=0; j<N/P;j++)
			{
				for (int k=0;k<N/P;k++)
				{
					_Resultat.table[i][j] =+ _A.table[i][k] * _B.table[k][j];
				}
			}
		}
		return _Resultat;
	}

	/* Test des contraintes d'intégrités liés a la parallélisation de l'algorithme*/
	int Verif()
	{
		if (Sdf::PROC_NB!=P*P)
		{
			if (Sdf::PROC_ID==0)
			{
				fprintf(Sdf::trace,"! Nombre de processeur incorrect \n",Sdf::PROC_ID);
				fflush(Sdf::trace);
			}
			return 0;
		}
		if (N<P)
		{ 
			if (Sdf::PROC_ID==0)
			{
				fprintf(Sdf::trace,"! Nombre de données N insufisante \n",Sdf::PROC_ID);
				fflush(Sdf::trace);
			}
			return 0;
		}
		if (N%P!=0)
		{
			if (Sdf::PROC_ID==0)
			{
				fprintf(Sdf::trace,"! Division de N/P non entiere \n",Sdf::PROC_ID);
				fflush(Sdf::trace);
			}
			return 0;
		}
		return 1;
	}
};

MAIN(Root_thread, init, Sdf::empty_f, Sdf::empty_e)
